#模拟退火法
import random
import math


def num_of_conflict(status): # 获取该状态下互相攻击的皇后对数
	num_of_conflict = 0;
	for col1 in range(0, 7):
		for col2 in range(col1+1, 8):
			if (status[col1] == status[col2]) \
			or ((col2 - col1) == abs(status[col1] - status[col2])) :  #判断是否相互攻击
				num_of_conflict += 1;
	return num_of_conflict



def get_next_num_of_conflict_status(status, T): #根据递减的T和当前状态返回一个新状态
	next_status = []
	
	for col in range(0,8):
		for row in range(0, 8):
			new_status = status[:]
			if status[col] != row:
				new_status[col] = row
				next_status.append(new_status)
	choose_status = random.randint(0, 55) #从56的邻居任选一个
	if num_of_conflict(next_status[choose_status]) <= num_of_conflict(status): #新的状态优于原先的
		return next_status[choose_status]
	else: #原先的状态优于新状态
		E = num_of_conflict(status) - num_of_conflict(next_status[choose_status])
		probability = math.e**(E/T) #概率计算公式
		choose = random.randint(0, 1000)/1000
		if choose <= probability: #以一定概率使新的状态取代原先的状态
			return next_status[choose_status]
	return status  #返回原状态，不移动







status = [0, 0, 0, 0, 0, 0, 0, 0]
for col in range(0, 8):
	row = random.randint(0, 7)
	status[col] = row
print("the initial status: ")
print(status)
print("the num of conflict: ")
print(num_of_conflict(status))
T = 5.0 #初始T，（温度）
while num_of_conflict(status) > 0 : #找不到最优解
	new_status = get_next_num_of_conflict_status(status, T) #获取新状态
	if new_status == status: #不移动
		print("E < 0, but no move")
	else: 
		status = new_status
		print("the new status: ")
		print(status)
		print("the num of conflict: ")
		print(num_of_conflict(status))
		if num_of_conflict(status) == 0:
			print("find a answer!")
	T = T * 0.99  # T递减，概率也递减
	if T < 0.0001:  #运行 1077 次，此时认为T接近0
		print("T = 0, can't find a answer")
		break







